package middle;

import util.PrintUtils;

public class Solution_304 {

    public static void main(String[] args) {
        NumMatrix model = new NumMatrix(new int[][]{{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}});
        System.out.println(model.sumRegion(0 ,1, 2, 2));
        System.out.println(model.sumRegion(2 ,1, 4, 3));
        System.out.println(model.sumRegion(1 ,1, 2, 2));
        System.out.println(model.sumRegion(1 ,2, 2, 4));
//        PrintUtils.transfer("[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]");
    }

    static class NumMatrix {

        private final int[][] arrays;

        public NumMatrix(int[][] matrix) {
            arrays = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++) {
                int row = 0;
                for (int j = 0; j < matrix[i].length; j++) {
                    row += matrix[i][j];
                    arrays[i][j] = row;
                    if (i > 0) {
                        arrays[i][j] += arrays[i-1][j];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return (row2 >= 0 && col2 >= 0 ? arrays[row2][col2] : 0)
                - (row1 > 0 && col2 >= 0 ? arrays[row1 - 1][col2] : 0)
                - (row2 >= 0 && col1 > 0 ? arrays[row2][col1 - 1] : 0)
                + (row1 > 0 && col1 > 0 ? arrays[row1 - 1][col1 - 1] : 0);
        }
    }
}
